﻿package test;

import java.util.Arrays;
import java.util.Random;

public class Base4 {
	public static void main(String[] args) {
		int nums[] = createNums();
		maoPao(nums);
		nums = createNums();
		xuanZe(nums);
		nums = createNums();
		chaRu(nums);
		nums = createNums();
		kuaiSu(nums, 0, nums.length - 1);
		System.out.println("快速："+Arrays.toString(nums));
	}

	// 快速排序
	private static void kuaiSu(int[] nums, int low, int high) {
		if (low < high) {
			int i = low;
			int j = high;
			int key = nums[i];
			while (i < j) {
				// 从后往前找第一个小于key的值
				while (i < j && nums[j] > key) {
					j--;
				}
				if (i < j) {
					// 这里直接替换,当然也可以在这里替换,但是不划算,一轮循环结束将key放入中间即可
					nums[i] = nums[j];
					i++;
				}
				// 从前往后找第一个大于key的值
				while (i < j && nums[i] < key) {
					i++;
				}
				if (i < j) {
					// 同上,直接替换
					nums[j] = nums[i];
					j--;
				}
			}
			// 一轮循环结束i=j,key肯定在中间
			nums[i] = key;
			kuaiSu(nums, low, i - 1);
			kuaiSu(nums, i + 1, high);
		}
	}

	// 插入排序
	private static void chaRu(int[] nums) {
		for (int i = 1; i < nums.length; i++) {
			for (int j = 0; j < i; j++) {
				if (nums[j] > nums[i]) {
					int tmp = nums[j];
					nums[j] = nums[i];
					nums[i] = tmp;
				}
			}
		}
		System.out.println("插入："+Arrays.toString(nums));
	}

	// 选择排序
	private static void xuanZe(int[] nums) {
		for (int i = 1; i < nums.length; i++) {
			int index = 0;
			for (int j = 1; j <= nums.length - i; j++) {
				if (nums[j] > nums[index]) {
					// index保存最大数的下标
					index = j;
				}
			}
			// 将最大数放到最后
			int tmp = nums[nums.length - i];
			nums[nums.length - i] = nums[index];
			nums[index] = tmp;
		}
		System.out.println("选择：" + Arrays.toString(nums));
	}

	// 冒泡排序
	private static void maoPao(int nums[]) {
		for (int i = 1; i < nums.length; i++) {
			for (int j = 0; j < nums.length - i; j++) {
				// 交换相邻两个数
				if (nums[j] > nums[j + 1]) {
					int tmp = nums[j];
					nums[j] = nums[j + 1];
					nums[j + 1] = tmp;
				}
			}
		}
		System.out.println("冒泡：" + Arrays.toString(nums));
	}

	// 随机产生数列
	private static int[] createNums() {
		int nums[] = new int[10];
		for (int i = 0; i < nums.length; i++) {
			nums[i] = new Random().nextInt(10);
		}
		return nums;
	}
}
